package com.lihui.binarytree;

import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @Author 比特就业课
 * @Date 2022-10-20
 */
public class BinaryTree {
    // 定义一个表示节点的类
    private static class TreeNode {
        int value; // 当前节点的值
        TreeNode left;  // 左子树的引用
        TreeNode right; // 右子树的引用
        // 构造方法

        public TreeNode(int value) {
            this.value = value;
        }
    }

    // 根节点的引用
    public TreeNode root;

    /**
     * 为了演示方便通过硬代码的方式创建一个二叉树
     * 后续不会通过这样的方式去创建二叉树
     */
    public void create () {
        // 先所有的节点创建出来
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        TreeNode node8 = new TreeNode(8);
        // 处理引用关系
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        // 指定根节点的引用
        root = node1;
    }

    // 前序遍历
    public void preOrder(TreeNode root) {
        // 如果是棵空树，直接返回
        if(root == null){
            return;
        }
        // 处理根节点
        System.out.print(root.value + " ");
        // 处理左子树
        preOrder(root.left);
        //处理右子树
        preOrder(root.right);
    }

    // 中序遍历
    public void inOrder(TreeNode root) {
        // 如果是棵空树，直接返回
        if(root == null){
            return;
        }
        //先处理左孩子
        inOrder(root.left);
        // 处理根节点
        System.out.print(root.value + " ");
        //处理右孩子
        inOrder(root.right);
    }

    // 后序遍历
    public void postOrder(TreeNode root) {
        // 如果是棵空树，直接返回
        if(root == null){
            return;
        }
        //处理左子树
        postOrder(root.left);
        //处理右子树
        postOrder(root.right);
        // 处理根节点
        System.out.print(root.value + " ");
    }

    /**
     * 获取树中节点的个数 - 子问题思路
     * @param root
     * @return
     */
    public int size(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return size1(root.left) + size1(root.right) + 1;
    }

    public int nodeSize;

    /**
     * 获取树中节点的个数 - 遍历思路
     * @param root
     * @return
     */
    public int size1(TreeNode root) {
        int count = 1;
        if(root == null){
            return 0;
        }
        count += size1(root.left);
        count += size1(root.right);
        return count;
    }

    /**
     * 获取叶子节点的个数 - 子问题
     * @param root
     * @return
     */
    public int getLeafNodeCount(TreeNode root) {
        if(root == null) {
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
    }

    public int leafCount;
    /**
     * 获取叶子节点的个数 - 遍历
     * @param root
     * @return
     */
    public int getLeafNodeCount1(TreeNode root) {
        if(root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            leafCount++;
        }
        getLeafNodeCount1(root.left);
        getLeafNodeCount1(root.right);
        return leafCount;
    }

// 子问题思路-求叶子结点个数

    // 获取第K层节点的个数
    public int getKLevelNodeCount(TreeNode root,int k) {
        if(root == null || k <= 0){
            return 0;
        }
        if(k == 1){
            return 1;
        }
          int left =   getKLevelNodeCount(root.left,k - 1);
          int right =  getKLevelNodeCount(root.right, k - 1);
        return left + right;
    }

    // 获取二叉树的高度
    public int getHeight(TreeNode root) {
        if(root == null){
            return 0;
        }
        int leftDepth = getHeight(root.left);
        int rightDepth = getHeight(root.right);
        int count = Math.max(leftDepth,rightDepth) + 1;
        return count;

    }

    // 检测值为value的元素是否存在
    public TreeNode find(TreeNode root, int val) {
        if(root == null){
            return null;
        }
        if(root.value == val){
            return root;

        }
        TreeNode leftVal = find(root.left,val);

        if(leftVal != null){
            return leftVal;
        }
        TreeNode rightVal = find(root.right,val);

        if(rightVal != null){
            return rightVal;
        }

        return null;
    }

    //层序遍历
    public void levelOrder(TreeNode root) {
        if(root == null){
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            System.out.print(node.value + " ");
            if(node.left != null){
                queue.offer(node.left);
            }

            if (node.right != null){
                queue.offer(node.right);
            }
        }
    }

    // 判断一棵树是不是完全二叉树
    public boolean isCompleteTree(TreeNode root) {
        if(root == null){
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
        TreeNode node = queue.poll();
        if(node != null){
            queue.offer(node.left);
            queue.offer(node.right);
        }else{
            while (!queue.isEmpty()){
                TreeNode checkNode = queue.poll();
                if(checkNode != null){
                    return false;
                     }
                }
            }
        }
        return true;
    }
}
